﻿using System;

namespace Algorithm.LeetCode
{
    /// <summary>
    /// 第五十三题：最大子序和
    /// </summary>
    public class No53
    {
        /*
         * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
         */

        public static int MaxSubArray(int[] nums)
        {
            var sum = int.MinValue;
            var count = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                count += nums[i];
                sum = Math.Max(sum, count);// 取区间累计的最大值（相当于不断确定最大子序终止位置）
                if (count <= 0)
                {
                    //抄的，有点不明白为啥要重置
                    count = 0;// 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
                }
            }
            return sum;
        }
    }
}
